ABC 425E

题目内容

求多项式系数 $(\binom{n}{c_{1}, c_{2}, \dots, c_{k}}) mod m$ ，其中 $n = \sum_{i = 1}^{k} c_{i}$ 。

特殊的数据范围： $m$ 为任意整数， $n \leq 5000$ 。

解法

提示一

$(\binom{n}{c_{1}, c_{2}, \dots, c_{k}}) = \prod_{i = 1}^{k} (\binom{n - \sum_{j = 1}^{i} c_{j}}{c_{i}}) = \prod_{i = 1}^{k} (\binom{\sum_{j = 1}^{i} c_{j}}{c_{i}})$

提示二

帕斯卡三角恒等式：

(\binom{n}{k}) = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k})

解答

两个提示给出的性质已经很明显了，依据提示二预处理出所有 $1 \leq i, j \leq 5000$ 的 $(\binom{i}{j})$ ，然后将多项式系数拆成多个二项式系数之积即可。

AC 代码

见提交记录。